package org.example.dynamic_planning;

import java.util.Arrays;
import java.util.Scanner;

public class Climb_the_stairs {
    public static void main(String[] args) {
        //爬楼梯进阶版

        //题目描述
        //假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
        //每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
        //注意：给定 n 是一个正整数。
        //输入描述
        //输入共一行，包含两个正整数，分别表示n, m
        //输出描述
        //输出一个整数，表示爬到楼顶的方法数。
        //输入示例
        //3 2
        //输出示例
        //3
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int j = 0; j <= n; j++) {
            for (int i = 1; i <= m; i++) {
                if (j>=i) dp[j] += dp[j-i];
            }
            System.out.println(Arrays.toString(dp));
        }
        System.out.println(dp[n]);
    }
}
